排列组合—算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

回溯算法的本质：它是一种深度优先搜索（DFS）的暴力枚举策略，核心是“尝试 - 回退”—— 在解决问题的过程中，一步步尝试所有可能的选择，当发现当前选择无法得到合法解时，就回退到上一步，撤销当前选择，继续尝试其他可能，直到找到所有解 / 一个合法解。

算法回顾

正因为回溯算法 “穷举 + 剪枝” 的特性，回溯算法特别适合解决 “组合 / 排列 / 子集类的搜索问题”、“约束满足类问题”（要求满足多个条件，且解空间是离散的），这类问题的共性是：
- 解由一系列选择组成，需要逐步构建；
- 存在无效选择（违反约束），需要及时回退；
- 解空间不大（或可通过剪枝大幅缩小），暴力枚举可接受。

排列组合子集问题

排列 / 组合 / 子集问题是回溯算法的 “入门级应用”，核心需求是从一组元素中，按指定规则找出所有满足条件的组合、排列或子集，关键区别在于：
- 组合：不考虑元素顺序（如从 [1,2,3] 选 2 个，[1,2] 和 [2,1] 是同一个）；
- 排列：考虑元素顺序（如从 [1,2,3] 选 2 个，[1,2] 和 [2,1] 是不同的）；
- 子集：找出所有可能的元素集合（包括空集和全集）。

核心解题思路
- 用递归实现 “一步步选择”：每一层递归代表 “选择第 k 个元素”；
- 用路径变量记录当前已选的元素（构建解的过程）；
- 用起始索引 / 标记数组避免重复选择（组合用起始索引，排列用标记数组）；
- 递归终止时，将路径加入结果集，完成一次有效解的搜索。

典型例题
- 组合总和（LeetCode 39）：从无重复数组中选数，和为目标值，数可重复选，找所有组合；
- 全排列（LeetCode 46）：求一个无重复数组的所有排列；
- 子集（LeetCode 78）：求一个无重复数组的所有子集；
- 组合（LeetCode 77）：从 1~n 中选 k 个元素，找所有组合。

教程目录导航

▼

排序问题

一、全排列（LeetCode 46）

问题描述：

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。
提示：
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- nums 中的所有整数互不相同
示例 1：
- 输入：nums = [1,2,3]
- 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
- 输入：nums = [0,1]
- 输出：[[0,1],[1,0]]

算法解析：

和组合总和的核心区别是：排列要求元素顺序不同则为不同解，且每个元素只能用一次，因此需要额外的标记数组记录元素是否已被选取，避免重复使用。

路径选择：遍历数组中未被选取的元素，加入当前排列路径，标记该元素为已使用；
终止条件：当当前路径的长度等于原数组长度时，说明生成了一个完整排列，加入结果集；
回溯还原：递归返回后，撤销当前选择（从路径中移除最后一个元素），并取消该元素的使用标记，继续尝试其他未被选取的元素；
无重复保证：因原数组无重复元素，且每个元素仅能被选取一次，无需额外去重逻辑。


#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> res_permute;  // 存储所有全排列结果
vector<int> path_permute;         // 存储当前正在构建的排列路径
vector<bool> used_permute;        // 标记数组：used_permute[i]表示第i个元素是否已被选取

// 回溯函数：nums-原数组
void permute(vector<int>& nums) {
    // 终止条件：路径长度等于数组长度，找到一个完整排列
    if (path_permute.size() == nums.size()) {
        res_permute.push_back(path_permute);
        return;
    }
    // 遍历所有元素，尝试选取未被使用的元素
    for (int i = 0; i < nums.size(); ++i) {
        if (used_permute[i]) continue; // 跳过已被选取的元素，核心去重/防重复使用
        used_permute[i] = true;        // 标记：选取当前元素
        path_permute.push_back(nums[i]);// 加入路径
        permute(nums); // 递归：继续构建排列
        path_permute.pop_back();       // 回溯：移除最后一个元素
        used_permute[i] = false;       // 回溯：取消标记，还原状态
    }
}

int main() {
    vector<int> nums = {1,2,3};
    used_permute.resize(nums.size(), false); // 初始化标记数组，全部为未使用

    permute(nums);
    for(vector<int> item : res_permute)
    {
        cout << "[";
        for(int node : item )
        {
            cout << " " << node << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}

输出结果


[ 1  2  3 ]
[ 1  3  2 ]
[ 2  1  3 ]
[ 2  3  1 ]
[ 3  1  2 ]
[ 3  2  1 ]

二、组合总和（LeetCode 39）

问题描述：

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
- candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
- 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
提示：
- 1 <= candidates.length <= 30
- 2 <= candidates[i] <= 40
- candidates 的所有元素互不相同
- 1 <= target <= 40
示例 1：
- 输入：candidates = [2,3,6,7], target = 7
- 输出：[[2,2,3],[7]]
- 解释：
  - 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
  - 7 也是一个候选， 7 = 7 。
  - 仅有这两种组合。
示例 2：
- 输入: candidates = [2,3,5], target = 8
- 输出: [[2,2,2,2],[2,3,3],[3,5]]

算法解析：

路径选择：从数组的指定位置开始选取元素，加入当前组合，目标值减去该元素值；
终止条件：若目标值减到 0，说明当前组合是有效解，加入结果集；若目标值小于 0，直接回溯（剪枝）；
回溯与剪枝：递归返回后，撤销当前选择（从组合中移除最后一个元素），继续尝试下一个元素；
去重关键：递归时从当前索引开始遍历，而非从 0 开始，避免生成重复组合（如 [2,3] 和 [3,2]）。


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> res; // 存储最终所有有效组合
vector<int> path;        // 存储当前正在构建的组合

// 回溯函数：candidates-原数组，target-剩余目标值，start-当前遍历起始索引
void backtrack(vector<int>& candidates, int target, int start) {
    // 终止条件1：剩余目标值为0，找到有效组合
    if (target == 0) {
        res.push_back(path);
        return;
    }
    // 终止条件2：剩余目标值小于0，剪枝（无需继续递归）
    if (target < 0) {
        return;
    }
    // 从start开始遍历，避免重复组合
    for (int i = start; i < candidates.size(); ++i) {
        path.push_back(candidates[i]); // 选择当前元素
        // 递归：剩余目标值减去当前元素，起始索引仍为i（可重复选取）
        backtrack(candidates, target - candidates[i], i);
        path.pop_back(); // 回溯：撤销选择，移除最后一个元素
    }
}

int main() {
    vector<int> candidates = {2,3,6,7};
    int target = 7;
    // 可选优化：排序后，若当前元素大于剩余target，可直接break（后续元素更大，无需遍历）
    sort(candidates.begin(), candidates.end());
    backtrack(candidates, target, 0);
    for(vector<int> item : res)
    {
        cout << "[";
        for(int node : item )
        {
            cout << " " << node << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}

输出结果


[ 2  2  3 ]
[ 7 ]

三、子集（LeetCode 78）

问题描述：

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
- 解集不能包含重复的子集。你可以按任意顺序返回解集。
提示：
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- nums 中的所有元素互不相同
示例 1：
- 输入：nums = [1,2,3]
- 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
- 输入：nums = [0]
- 输出：[[],[0]]

算法解析：

核心思路和组合总和相似，但终止条件更灵活 ——遍历过程中每一个路径都是有效子集，无需等目标值达标或路径长度满额，直接收集即可。

路径选择：从数组的指定start索引开始选取元素，加入当前子集路径，保证子集元素按数组顺序选取；
结果收集：每一步递归的路径都是一个有效子集（包括空集），进入递归后直接将当前路径加入结果集，这是本题和组合、排列的核心区别；
终止条件：当start遍历到数组末尾时，无元素可选，递归自然返回（无需显式终止条件）；
去重关键：递归时从当前 start 索引开始遍历，而非 0，避免生成重复子集（如[1,2]和[2,1]视为同一个子集，需排除）；
回溯还原：递归返回后，撤销当前选择（从路径中移除最后一个元素），继续尝试下一个元素。


#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> res_subsets;  // 存储所有子集结果
vector<int> path_subsets;         // 存储当前正在构建的子集路径

// 回溯函数：nums-原数组，start-当前遍历的起始索引（核心去重）
void subsets(vector<int>& nums, int start) {
    res_subsets.push_back(path_subsets);  // 关键：每一步路径都是有效子集，先收集再递归
    // 从start开始遍历，避免重复子集
    for (int i = start; i < nums.size(); ++i) {
        path_subsets.push_back(nums[i]);  // 选择：加入当前元素
        subsets(nums, i + 1);   // 递归：下一个元素从i+1开始（不可重复选）
        path_subsets.pop_back();          // 回溯：撤销选择，还原状态
    }
}

int main() {
    vector<int> nums = {1,2,3};

    subsets(nums, 0);
    for(vector<int> item : res_subsets)
    {
        cout << "[";
        for(int node : item )
        {
            cout << " " << node << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}

输出结果


[]
[ 1 ]
[ 1  2 ]
[ 1  2  3 ]
[ 1  3 ]
[ 2 ]
[ 2  3 ]
[ 3 ]

返回顶部